package algorithm;

import java.util.Arrays;

/**
 * @Description: 计数排序
 * @Author: hmm
 * @CreateDate: 2019/8/27
 * @UpdateUser:
 * @UpdateDate: 2019/8/27
 * @UpdateRemark: 修改备注
 * @Version: 1.0
 */
public class CountingSort {
    /**
     * 计数排序
     *
     * @param array
     * @return
     */
    public static int[] countingSort(int[] array) {
        if (array.length == 0) {
            return array;
        }
        int bias, min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int i = 0; i < array.length; i++) {
            max = Math.max(max, array[i]);
            min = Math.min(min, array[i]);
        }
        //计算偏移量，将 min ~ max 映射到 bucket 数组的 0 ~ (max - min) 位置上
        bias = -min;
        int[] bucket = new int[max - min + 1];
        Arrays.fill(bucket, 0);
        for (int i = 0; i < array.length; i++) {
            bucket[array[i] + bias]++;
        }
        int index = 0, i = 0;
        while (index < array.length) {
            if (bucket[i] != 0) {
                array[index] = i - bias;
                bucket[i]--;
                index++;
            } else {
                i++;
            }
        }
        return array;
    }

    public static void main(String[] args) {
        int[] arr = {1,6,2,41,11,25,8,31,25,22};
        countingSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
